package com.cty.LinkedList;

/*
* 创建一个环形链表
* */
public class CircleSingleLinkedList {
    private Boy first = null;//创建第一个节点
    //创建一个添加节点的方法(参数是添加个数)
    public void addBoy(int nums) {
        //判断nums的值是否正确
        if (nums <= 1) {
            System.out.println("nums的值不正确");
            return;
        }
        //创建一个辅助指针，用于遍历到环形链表的最后一个节点（下一个节点是first节点，因为是循环链表）
        Boy temp = null;
        //循环添加到圈中
        for (int i = 1; i <= nums; i++) {
            //创建一个小孩并赋予编号
            Boy boy = new Boy(i);
            //判断编号是否为1
            if (i == 1) {
                first = boy;
                boy.next = first;
                temp = first;
            } else {
                temp.next = boy;
                boy.next = first;
                temp = boy;//让temp等于最后一个节点
            }
        }
    }

    //创建一个遍历约瑟夫环的方法
    public void showBoy() {
        if (first == null) {
            System.out.println("没有小孩~~");
            return;
        }
        //创建一个辅助指针用于遍历链表
        Boy temp = first;
        while (true) {
            System.out.printf("小孩的编号 %d \n", temp.getNo());
            //环形链表已经遍历完毕
            if (temp.next == first) {
                break;
            }
            temp = temp.next;
        }
    }
    //约瑟夫问题的出圈方法(创建一个n个小孩的环，从第k个小孩开始数，数m个数出圈)
    public void delete(int n,int k,int m) {
        if (n <= 1 || k < 1 || k >= n || m < 1) {
            System.out.println("规则有误，无法进行游戏");
            return;
        }
        //调用增加方法
        addBoy(n);
        //创建一个辅助指针用于指向删除节点的前一个节点
        Boy temp = first;
        //将辅助节点指向first节点的前一个节点
        while (temp.next != first) {
            temp = temp.next;
        }
        for (int i =1;i <= k-1; i++) {
            temp = temp.next;
            first = first.next;
        }
        while (true) {
            //判断圈中是否只剩一个
            if (temp == first) {
                System.out.printf("最后一个出圈的小孩编号 %d",first.getNo());
                break;
            }
            for (int i = 1; i <= m - 1; i++) {
                temp = temp.next;
                first = first.next;
            }
            System.out.printf("出圈的小孩编号 %d\n", first.getNo());
            first = first.next;
            temp.next = first;
        }
    }
}
